/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/word-ladder
   @Language: C++
   @Datetime: 16-02-09 08:51
   */

class Solution {	
public:
	/**
	 * @param start, a string
	 * @param end, a string
	 * @param dict, a set of string
	 * @return an integer
	 */
	int ladderLength(string &start, string &end, unordered_set<string> &dict) {
		// write your code here	
		if (start==end) return 1;
		queue<string> que;
		int len=1;
		for(que.push(start); que.size(); ++len){
			int size = que.size();
			for(int i=0; i<size; ++i, que.pop()){
				string &str=que.front();
				for(int j=0; j<str.length(); ++j){
					string s=str;       // preserve str
					for(char c='a'; c<='z'; ++c){
						if (str[j]==c) continue;	// skip
						s[j]=c;
						if (s==end) return len+1;
						if(dict.find(s)==dict.end()) continue;
						que.push(s);
						dict.erase(s);	// avoid dead loop
					}
				}
			}
		}
		return 0;
	}
};
